import numpy as np
from function import RandomizedQuickSort
import time
import re
import matplotlib.pyplot as plt


def analysisBinarySearch(a, x, n, count):
    l = 0
    r = n - 1
    while l <= r:
        count[0] += 1
        mid = int((l + r) / 2)
        if a[mid] == x:
            return mid
        elif a[mid] > x:
            r = mid - 1
        elif a[mid] < x:
            l = mid + 1

    return -1


def BinSearchAnalysis(N):
    x = list(range(1, N + 1))
    n = len(x)
    y1 = []
    y2 = []
    for item in x:
        start = time.time()
        count = [0]
        analysisBinarySearch(x, item, n, count)
        cost = time.time() - start
        y1.append(cost)
        y2.append(count[0])
    print("查询", x, "\n耗时", y1)
    print("比较次数", y2)
    plt.plot(x, y2, label='compareCountLine', linewidth=2, color='r', marker='o',
             markerfacecolor='blue', markersize=10)
    plt.plot(x, y1, label='costLine')
    plt.title('analysis')
    plt.xlabel('searchElem')
    plt.ylabel('cost')
    plt.legend()
    plt.show()


def SortAnalysis(nRange=None):
    if nRange is None or len(nRange) == 0:
        nRange = [10, 100, 500, 1000, 10000]
        print("未输入数据，使用默认的数据量进行测试，数据量分别为", nRange)
    for n in nRange:
        x = []
        y = []
        tmp_l = n//10
        while tmp_l <= n:
            a = np.empty([tmp_l], dtype=int)
            start = time.time()
            try:
                RandomizedQuickSort(a, 0, len(a) - 1)
            except Exception:
                print("数据量过多，栈溢出")
                exit()
            cost = time.time() - start
            x.append(tmp_l)
            y.append(cost)
            tmp_l += n//10
        print("测试的随机产生的不同数组的长度：", x, "\n对应的排序耗费时间：", y)
        plt.plot(x, y, label="costLine")
        plt.title('analysis')
        plt.xlabel('X the ArrayData Size')
        plt.ylabel('Y algorithm cost time')
        plt.legend()
        plt.show()


if __name__ == "__main__":
    print("任意输入：对二分搜索进行测试分析\n"
          "直接回车：对快速排序进行测试分析")
    tmp = input("请输入:")
    if tmp.__len__() > 0:
        tmp_n = input("输入测试次数（默认为1次）:")
        try:
            if tmp_n.__len__() == 0:
                N = input("输入要测试的数据量（整数）:")
                N = int(N)
                BinSearchAnalysis(N)
            else:
                tmp_n = int(tmp_n)
                while tmp_n > 0:
                    N = input("输入要测试的数据量（整数）:")
                    try:
                        N = int(N)
                        BinSearchAnalysis(N)
                    except Exception:
                        print("输入错误！")
                        exit()
                    tmp_n -= 1
        except Exception:
            print("输入错误！请按要求输入")
            exit()
    else:
        nRange = input("请输入要测试的数据量(整数，不输入时使用默认数据量测试)")
        regx = "[0-9]+"
        list_in = re.findall(regx, nRange)
        nRange = [int(x) for x in list_in]
        SortAnalysis(nRange)
